1. Field of the Invention
This invention relates to the field of processing and/or communications, and in particular to the control of a buffer for interfacing between two systems, one of which is configured to access the buffer in a non-sequential manner.
2. Description of Related Art
Buffers are commonly used to interface between systems, particularly systems that transfer data asynchronously. Such a data transfer buffer is generally configured to receive data, either synchronously or asynchronously, from a first system, and to provide it to a second system, on demand from the second system. A buffer manager is used to assure that the data is received from the first system before a corresponding data item is provided to the second system. That is, the buffer manager regulates the speed at which a receiver can receive data to a corresponding speed of a transmitter that is sending the data.
FIG. 1 illustrates an example buffer 100 that is configured to store each data item from a transmitting system, at a location indicated by a write pointer 110. As each data item is stored, the write pointer 110 is incremented, to indicate the location to store the next data item. Data is provided to a receiving system by initializing a read pointer 120 to be equal to the write pointer 110, and then sequentially providing each data item to the receiving system upon request. As each data item is provided to the receiving system, the read pointer 120 is incremented, to indicate the location of the next available data item. To assure that the read pointer 120 does not point to a location that has not yet been written to, the read pointer 120 is constrained to not exceed a limit 130. This limit is continually adjusted as the data items are stored in the buffer 100, and conventionally corresponds to the write pointer 110. For ease of reference and understanding, the limit 130 is discussed hereinafter as a specific parameter, even though it may be the same parameter as the write pointer 110.
The limit 130 is enforced either by a memory access controller, or directly by the receiving system. That is, commonly the limit 130 is made available by the memory access controller, and it is the receiving system's responsibility to maintain the read pointer 120 and to assure that it does not “track” beyond the limit 130.
Generally, the buffer 100 is finite in size, and substantially smaller than the total number of data items that may be received by the buffer 100. To allow for continued use of the buffer, the buffer is generally configured to be “circular”, such that when a pointer reaches the end of the buffer, it is reset to the beginning of the buffer. Algorithms are commonly available for enforcing the aforementioned limit 130 within a circular buffer. Depending upon the particular embodiment, the write pointer 110 may also be constrained so as not to track beyond a limit corresponding to the read pointer 120 after it loops around the circular buffer. That is, the transmitting system will be prevented from storing data into the buffer 100 if the prior data has not yet been read by the receiving system. Alternatively, the read pointer 120 can be forced to advance, to keep ahead of the write pointer as new data arrives, the unread data being overwritten by the newly arriving data. For ease of reference and understanding, the invention is presented hereinafter with regard to the enforcement of a limit on the read pointer, the enforcement of a limit on the write pointer 110 being substantially equivalent.
The size of the buffer 100 determines the allowable mis-match between the speed of writing and reading to and from the buffer, and/or in the case of an uncontrolled transmitter, the size of the buffer 100 determines the amount of data lost due to a mis-match of speeds between the transmitter and the receiver. In the case of a controlled transmitter, the buffer 100 serves to enforce an equalization of the average transmit and receive data rates, and the size of the buffer 100 determines the degree of variance allowed about this average data rate.
As noted above, the system that provides the data to the buffer 100, and the system that receives the data from the buffer 100 are asynchronous. The updating of the limit 130, therefore, can only be synchronous with one or the other system. To assure that the pointers or limit are not misread as they are incremented, the pointers are commonly encoded and incremented using a gray-code, wherein only one bit of the pointer changes during an incremental transition. In this manner, an asynchronous read of the limit 130 at the time of transition of the limit 130 will either provide the prior value or the next value of the limit 130. Because enforcement of the prior value of the limit 130 will still prevent the read pointer 120 from tracking beyond the write pointer 110, the use of a gray-code sequence assures the integrity of the read process, regardless of when the limit 130 is read.
This conventional two-port (data-in, data-out) buffer scheme for asynchronous read and write access assumes as a basic premise that the writing of data to the buffer 100 is sequential. That is, it is inherently assumed that all of the memory locations between the read pointer 120 and the limit 130 contain valid data. In some applications, discussed further below, data may be more efficiently made available for writing to a buffer in a somewhat non-sequential manner.